// 3_The Kth largest element in the array.cpp : Defines the entry point for the console application.
//在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
/*
示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
说明:

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。*/
#include "stdafx.h"
#include<iostream>
using namespace std;
int length(int *a)
{
	int x=0;
	while(abs(*a)<100000){
		a++;
		x++;
	}
	return x;
}
void copy(int *a,int *b)
{
	for(int i=0;i<length(a);i++){
		b[i]=a[i];
	}
}
int maxk(int *a,int k)
{
    // FIXME: 除了排序算法之外，还有什么其他的方法？
	int n=length(a);int t;int *p=a;
	for(int i=0;i<n;i++){
		for(int j=i;j<n;j++){
			if(*(p+i)<=*(p+j)){
				t=*(p+i);
				*(p+i)=*(p+j);
				*(p+j)=t;
			}
		}
	}
	return *(p+k-1);		
}

void main()
{
	int a[]={1,2,3,11,4,5,6,7,7,8,9,8,10,1,0,5,2,5,5,5,1};int k=2;
	int n=length(a);
	int b[100];copy(a,b);
	int t=maxk(b,k);
	cout<<"the array you input is: ";
	for(int i=0;i<n;i++){
		cout<<a[i]<<" ";
	}
	cout<<endl<<"第 "<<k<<" 个最大的元素为 "<<t<<endl;
}
